/**
 * 
 */
package com.gwcloud.leetcode.hot100;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName   : Leetcode0560 
 * @author      : ganwei 
 * @date        : 2020年5月23日
 * @Description : Leetcode0560 和为K的子数组
 */
public class Leetcode0560 {
	int result = 0;
	/**
	 * -解题思路,暴力解法,性能垃圾，但是好使
	 */
    public int subarraySum(int[] nums, int k) {
    	for(int i = 0; i < nums.length; i++){
    		int sum = 0;
    		for(int j = i; j < nums.length; j++){
    			sum += nums[j];
    			if(sum > k){
    				continue;
    			}else if(sum == k){
    				result += 1;
    			}
    		}
    	}
        return result;
    }
    public int subarraySum_1(int[] nums, int k) {
        // key：前缀和，value：key 对应的前缀和的个数
        Map<Integer, Integer> preSumFreq = new HashMap<>();
        // 对于下标为 0 的元素，前缀和为 0，个数为 1
        preSumFreq.put(0, 1);

        int preSum = 0;
        int count = 0;
        for (int num : nums) {
            preSum += num;

            // 先获得前缀和为 preSum - k 的个数，加到计数变量里
            if (preSumFreq.containsKey(preSum - k)) {
                count += preSumFreq.get(preSum - k);
            }

            // 然后维护 preSumFreq 的定义
            preSumFreq.put(preSum, preSumFreq.getOrDefault(preSum, 0) + 1);
        }
        return count;
    }


    
    /**
     * -主函数
     */
    public static void main(String[] args){
    	
    }
}
